package com.canopys.study.open.test.algorithm.dynamic;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Stack;

/**
 * @Author: Canopys
 * @Descrption:
 * @Date: Created in 22:22 2020/5/8
 * @Modified By:
 */
public class IsMatch {

    public static Map<Integer, Integer> map = new HashMap<>();
    public static Map<Integer, Integer> map2 = new HashMap<>();
    public static Map<Integer, Integer> map1 = new HashMap<>();
    public static Map<Integer, Integer> mapR1 = new HashMap<>();

    public static boolean isMatch(String s, String p) {
        if (s == null && p != null) {
            return false;
        }

        if (s != null && p == null) {
            return false;
        }

        if (s == null && p == null) {
            return true;
        }
        int sLength = s.length();
        int pLength = p.length();
        char preChar = '0';
        int i = 0, j = 0;
        for (; i < sLength && j < pLength; i++) {
            if (s.charAt(i) == p.charAt(j)) {
                preChar = s.charAt(i);
                j++;
                continue;
            } else {
                if ('.' == p.charAt(j)) {
                    preChar = s.charAt(i);
                    j++;
                } else if ('*' == p.charAt(j)) {
                    if (s.charAt(i) != preChar && preChar != '.') {
                        j++;
                        i--;
                    }
                } else {
                    return false;
                }
            }
        }

        if (i == sLength && j == pLength) {
            return true;
        } else if (i != sLength) {
            return false;
        } else {
            for (; j < pLength; j ++) {
                if (p.charAt(j) != '*' && p.charAt(j) != '.') {
                    return false;
                }
            }
            return true;
        }
    }

    //public static int findCattle

    /**
     *
     * @param n 农夫坐标
     * @param k 牛坐标
     * @return
     */
    public static int findCattle(int n, int k) {
        if (k <= n) {
            return n - k;
        }

        if (map.containsKey(n)) {
            return map.get(n);
        }

        int move2 = map2.containsKey(n) ? map2.get(n) : findCattle(2*n, k);
        map2.put(n, move2);
        if (map1.containsKey(n)) {
            System.out.println(map1.get(n));
        }
        int move1 =  map1.containsKey(n) ? map1.get(n) : findCattle(n + 1, k);
        map1.put(n, move1);

        int moveR1 = mapR1.containsKey(n) ? mapR1.get(n) : findCattle(n - 1, k);
        mapR1.put(n, moveR1);

        int min = Math.min(Math.min(move1, move2), moveR1);
        map.put(n, min);

        return min + 1;

    }

    public static int calculate(String s) {
        int length = s.length();
        Stack<String> stack = new Stack<>();
        Stack<Character> opStack = new Stack<>();
        StringBuilder sb = null;
        for (int i = 0; i < length; i++) {
            Character c = s.charAt(i);
            if ('0' <= c && c <= '9') {
                if (sb == null) {
                    sb = new StringBuilder(c.toString());
                } else {
                    sb.append(c);
                }
            } else if ('-' == c || '+' == c) {
                opStack.push(c);
                if (null != sb) {
                    stack.push(sb.toString());
                    sb = null;
                }
            } else if ('(' == c) {
                if (null != sb) {
                    stack.push(sb.toString());
                    sb = null;
                }
                stack.push(c.toString());
            } else if (')' == c){
                if (sb != null) {
                    stack.push(sb.toString());
                    sb = null;
                }

                int sum = 0;
                String num = null;
                while (!"(".equals(num = stack.pop())) {
                    if (!opStack.isEmpty()) {
                        Character opC = opStack.pop();
                        if ('-' == opC) {
                            sum -= Integer.valueOf(num);
                        } else if ('+' == opC) {
                            sum += Integer.valueOf(num);
                        }
                    } else {
                        sum += Integer.valueOf(num);
                    }
                }
                stack.push(String.valueOf(sum));
            }
        }
        if (sb != null) {
            stack.push(sb.toString());
        }
        //Long.to

        int sum = 0;
        String num = null;
        while (!stack.isEmpty()) {
            num = stack.pop();
            if (!opStack.isEmpty()) {
                Character opC = opStack.pop();
                if ('-' == opC) {
                    sum -= Integer.valueOf(num);
                } else if ('+' == opC) {
                    sum += Integer.valueOf(num);
                }
            } else {
                sum += Integer.valueOf(num);
            }
        }

        return sum;

    }

    public static boolean isValidSerialization(String preorder) {
        Stack<Integer> stack = new Stack<>();
        int length = preorder.length();

        stack.push(1);
        boolean perIsNum = true;
        for (int i = 0; i < length; i++) {
            if (stack.isEmpty()) {
                return false;
            }

            Character c = preorder.charAt(i);
            if (',' == c && perIsNum) {
                int num = stack.pop();
                if (num == 1) {
                    stack.push(2);
                } else if (num == 2) {
                    stack.push(2 - 1);
                    stack.push(2);
                }
            } else if ('#' == c) {
                perIsNum = false;
                int num = stack.pop();
                if (num == 1) {

                } else if (num == 2) {
                    stack.push(2 - 1);
                }
            } else if ('0' <= c && c <= '9') {
                perIsNum = true;
            }
        }

        if (stack.isEmpty()) {
            return true;
        } else {
            return false;
        }

    }

    public static int[][] generateMatrix(int n) {
        int[][] matrix = new int[n][n];

        int row = 0;
        int col = 0;
        int rowDir = 0;
        int colDir = 1;
        matrix[0][0] = 1;
        for (int i = 2; i <= n * n; i++) {
            if (row >= n || col >= n) {
                return matrix;
            }
            if (0 <= row + rowDir && row + rowDir < n
                    && 0 <= col + colDir && col + colDir < n
                    && matrix[row + rowDir][col + colDir] == 0) {

            } else if (col + 1  >= n || matrix[row][col + 1] != 0) {
                rowDir = 1;
                colDir = 0;
            } else if (row + 1 >= n || matrix[row + 1][col] != 0) {
                rowDir = 0;
                colDir = -1;
            } else if (col - 1 < 0  || matrix[row][col - 1] != 0) {
                rowDir = -1;
                colDir = 0;
            } else if (row - 1 < 0 || matrix[row - 1 ][col] != 0) {
                rowDir = 0;
                colDir = 1;
            }

            row += rowDir;
            col += colDir;
            matrix[row][col] = i;
        }

        return matrix;

    }

    public static int count = 0;
    public static Map<String, Boolean> mapFind = new HashMap<>();
    public static void find(String s, int startS, String t, int startT) {
        int tLength = t.length();
        int sLength = s.length();

        if (tLength == startT) {
            count++;
            return;
        }

        if (sLength == startS) {
            return;
        }

        Character c = t.charAt(0);
        if (!s.contains(c.toString())) {
            return;
        }

        int startTT = 0;
        for (int i = 0; i < sLength; i++) {
            if (s.charAt(i) == t.charAt(0)) {
                if (!mapFind.containsKey(i + "_" + tLength)) {
                    find(s, i + 1, t, startTT++);
                    mapFind.put(i + "_" + tLength, true);
                }
                if (!mapFind.containsKey((i + 1) + "_" + tLength)) {
                    find(s, i + 1, t, startTT);
                    mapFind.put((i + 1) + "_" + tLength, true);
                }

            }
        }
    }

    public static void main(String[] args) {
        /*String s1 = "aaaabbbcceee";
        String p1 = "a.*";
        String p11 = "aaa.bb*cceee";
        String p12 = ".*";
        String p13 = "aaaabbbcce*";
        System.out.println(isMatch(s1, p1));
        System.out.println(isMatch(s1, p11));
        System.out.println(isMatch("ab", p12));
        System.out.println(isMatch(s1, p13));*/

        //int n = findCattle(5, 17);
        //System.out.println(n);

        //calculate("1 + 1");
        //System.out.println(calculate("- (3 + (4 + 5))"));
        //isValidSerialization("9,3,4,#,#,1,#,#,2,#,6,#,#");

        //generateMatrix(3);
        //find("bbb", "bb");

        System.out.println(count);
    }
}
